package leetcode.editor.cn;

//Java：环形链表 II
public class LinkedListCycleIi {
    public static void main(String[] args) {
        Solution solution = new LinkedListCycleIi().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
    /**
     * 思路：需要找到环的切入点，切入点的计算需要理解：即从相遇的位置到切入点和从头节点到切入点的距离相同。即如果快慢指针的速度是2倍的关系，最后的等式为：x=z;
     * 1、假设从头节点到环切入点的距离为x，切入点到相遇点距离为y，相遇点到前方切入点为Z。
     * 因为快指针速度是慢指针的2倍，所以快慢指针相遇的时候有如下关系：
     * slow=x+y;fast=x+y+n(z+y); 即2（x+y）=x+y+n(z+y) -> x=(n-1)(z+y)+z。 （n-1)(z+y)为圈数，所以可得x=z;
     * <p>
     * 问题一：循环的时候fast是跳两个节点，为什么判断的不是fatsNode.next!=null&&fastNode.next.next!=null?
     * 答：因为极限情况只有两个节点，即fastNode != null && fastNode.next != null，这种两个节点的情况也是存在环的情况，需要进入循环判断。而不是直接返回null
     * 同时进行指针指向的时候需要避免空指针，因为fastNode比较快，所以要做好，快指针的非空校验。 根据fastNode = fastNode.next.next;快指针需要的非空对象为fastNode和fastNode.next
     */
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            ListNode fastNode = head;
            ListNode slowNode = head;
            while (fastNode != null && fastNode.next != null) {
                slowNode = slowNode.next;
                fastNode = fastNode.next.next;
                if (slowNode == fastNode) {
                    ListNode index1 = fastNode;
                    ListNode index2 = head;
                    while (index2 != index1) {
                        index2 = index2.next;
                        index1 = index1.next;
                    }
                    return index2;
                }
            }
            return null;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}